package basis.netease.medium;

import java.util.*;

/**
 * 7-7 连通网络的操作次数
 * 用以太网线缆将 n 台计算机连接成一个网络，计算机的编号从 0 到 n-1。线缆用 connections 表示，其中 connections[i] = [a, b] 连接了计算机 a 和 b。
 * 网络中的任何一台计算机都可以通过网络直接或者间接访问同一个网络中其他任意一台计算机。
 * 给你这个计算机网络的初始布线 connections，你可以拔开任意两台直连计算机之间的线缆，并用它连接一对未直连的计算机。请你计算并返回使所有计算机都连通所需的最少操作次数。如果不可能，则返回 -1 。
 * 输入格式:
 * 第 1 行输入 n 和 m，分别表示计算机的个数和线缆个数，用空格分隔。接下来的 m 行输入，表示有线缆连接的计算机 a 和 b，用空格分隔。
 * 输出格式:
 * 对每一组输入，在一行中输出使所有计算机都连通所需的最少操作次数，如果不可能，则返回-1。
 * 输入样例1:
 * 如图所示：
 * 例子.png
 * 这里相应地给出一组输入：
 * 输入样例1:
 * 4 3
 * 0 1
 * 0 2
 * 1 2
 * 输出样例1:
 * 在这里给出相应的输出。例如：
 * 1
 * 解释：拔下计算机 1 和 2 之间的线缆，并将它插到计算机 1 和 3 上。
 * 输入样例2:
 * 6 4
 * 0 1
 * 0 2
 * 0 3
 * 1 2
 * 输出样例2:
 * 在这里给出相应的输出。例如：
 * -1
 * 解释：线缆数量不足。
 * 提示
 * 1 <= n <= 10^5
 * 1 <= connections.length <= min(n*(n-1)/2, 10^5)
 * connections[i].length == 2
 * 0 <= connections[i][0], connections[i][1] < n
 * connections[i][0] != connections[i][1]
 * 没有重复的连接。
 * 两台计算机不会通过多条线缆连接。
 */
public class Main_7 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String input = in.nextLine();
        int computerCount = Integer.parseInt(input.split(" ")[0]);
        int cableCount = Integer.parseInt(input.split(" ")[1]);
        // 初始化并查集
        int[] parent = new int[computerCount];
        for (int i = 0; i < computerCount; i++) {
            parent[i] = i;
        }
        // 将两台计算机相连
        for (int i = 0; i < cableCount; i++) {
            String temp = in.nextLine();
            int from = Integer.parseInt(temp.split(" ")[0]);
            int to = Integer.parseInt(temp.split(" ")[1]);
            union(parent, from, to);
        }
        if (cableCount < computerCount - 1) {
            System.out.println(-1);
            return;
        }
        // 算出根节点，即为连通分量
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < computerCount; i++) {
            set.add(find(parent, i));
        }
        // 最少操作次数为连通分量减1
        System.out.println(set.size() - 1);
    }

    private static int find(int[] parent, int x) {
        // 路径压缩
        if (parent[x] != x) {
            parent[x] = find(parent, parent[x]);
        }
        return parent[x];
    }

    private static void union(int[] parent, int x, int y) {
        int rootX = find(parent, x);
        int rootY = find(parent, y);
        if (rootX != rootY) {
            parent[rootX] = rootY;
        }
    }

}
